\chapter{Chores}

\begin{itemize}

\item{The RunDelayed Interface}

\item{Futures}

\item{FutureFactory}

\item{Chore-programming Techniques}

\item{Macro Dataflow Examples: Vector Addition}

\item{Chore Examples: Warshall's Algorithm}

\end{itemize} We gain two large advantages from the use of threads:

\begin{itemize}

\item{We can make use of multiple processors (assuming that we have native
threads and several processors available).}

\item{We can continue running parts of our computation when other parts are
blocked waiting for data to become available. This is particularly the case when
running distributed computations on computer networks, as we will discuss in
later chapters.}

\end{itemize} Threads come with a cost, however. They take time to create, and
they occupy a large amount of storage.

We use \texttt{RunQueue} objects to reuse threads, saving us the expense of
creating them over and over. But the cost of creating threads repeatedly is only
part of the problem. A danger of parallel computation is having too much
parallelism--in our case, too many threads. We also want to avoid filling our
memory with threads.

\texttt{RunQueue} objects have the ability to limit the number of threads that
can be created, which can help us throttle the computation and avoid the danger
of flooding memory with threads, but that leads to another danger, deadlock. All
the threads created by the run queue may be waiting for conditions that only
runnables still on the run queue can cause, but those runnables cannot execute
because the run queue will not allow any more threads to be created.

We will try to overcome this problem by breaking our computation into chores
that we put in their own runnables. Recall in the last chapter we defined the
concept of a chore as a small amount of computation which communicates with
other chores only at its beginning and its end. A thread running a chore does
not wait in the middle of its computation for another thread to cause a
condition.

Rather than assigning paths of chores to threads, we use a different approach in
which we make each chore a separate \texttt{Runnable} object and drop it into a
run queue when its predecessors have completed. These chores can run to
completion and then give up the thread they are running on. The threads then
remove and run other chores from the run queue. Since threads are not suspended
awaiting completion of chores in other threads, fewer threads are needed
overall.

Here's how we intend to use chores to throttle our computation:

\begin{itemize}

\item{We will pack chores in runnables. Conceptually, we would like a single
kind of chore to have a single runnable class, but later, again for efficiency,
we will consider how to reuse runnable objects for more than one chore.}

\item{We will provide facilities for chores to be delayed on various kinds of
synchronization objects (e.g., Future , Barrier , and TerminationGroup
objects).}

\item{While delayed, the chore gives up not only the processor, but the thread
that is running it.}

\item{Chores are placed in a run queue to be allocated a thread to execute them.
Chores can wait for multiple conditions before they start their main
computation, but they can't hold on to the thread while waiting. We'll see how
to program this. A chore will run to completion once its main computation has
begun.}

\item{Because chores will not hold onto threads, chores can be scheduled in run
queues with a limit on the number of threads that can be created. This will
effectively throttle the computation.}

\end{itemize} Naturally, there are problems with using chores in this way.
Chores can be quite small. A multitude of small chores can be expensive to
create and schedule. Grain size should always be taken into account when
breaking a computation into chores. It might be more efficient just to use
straight threads for parts of the computation. Also, a proliferation of chores
can result in a proliferation of class definitions with obscure interactions.

\section{The RunDelayed Interface} Scheduling chores is based in the
\texttt{RunDelayed} interface. The interface \texttt{RunDelayed} defines the
single method \texttt{void runDelayed(Runnable)} . It is implemented by all
classes that provide a \texttt{runDelayed()} method.

% tabular

\textbf{\texttt{interface RunDelayed \lbrack}} interface
RunDelayed \lbrack \begin{verbatim}





public void runDelayed(Runnable)

	\end{verbatim}

 \begin{verbatim}



}

	\end{verbatim}



 %\end{tabular}

 Method \texttt{runDelayed(r)} will cause
	runnable \texttt{r} to be placed in a run queue when some condition is
	satisfied.

\section{Futures} The class \texttt{Future} is an extension of
\texttt{SimpleFuture} that implements \texttt{RunDelayed} . All the operations
on \texttt{SimpleFuture} will also work on \texttt{Future} s.

%\begin{tabular}

 \textbf{\texttt{Future}} Futureconstructors and methods
\textbf{\texttt{Future()}} Future()creates a \texttt{Future} object with no
value yet assigned. \textbf{\texttt{Future(java.lang.Object val)}}
Future(java.lang.Object val)creates a \texttt{Future} object with a value
initially assigned. \textbf{\texttt{java.lang.Object getValue()}}
java.lang.Object getValue()waits until a value has been assigned to the
\texttt{Future} object and then returns it. \textbf{\texttt{boolean isSet()}}
boolean isSet()checks to see if a value has been assigned to the \texttt{Future}
object yet. \textbf{\texttt{void setValue(java.lang.Object val)}} void
setValue(java.lang.Object val)assigns a value to the \texttt{Future} object,
notifies all waiting threads, and schedules all run-delayed runnables.
\textbf{\texttt{static RunQueue getClassRunQueue()}} static RunQueue
getClassRunQueue()gets the \texttt{RunQueue} object for the \texttt{Future}
class. This is the run queue that will be used for chores that are run delayed
on a \texttt{Future} object unless \texttt{setRunQueue()} has been called to
assign a different run queue. \textbf{\texttt{void runDelayed(java.lang.Runnable
r)}} void runDelayed(java.lang.Runnable r)schedules a \texttt{Runnable} object
to execute when the \texttt{Future} object has its value set. When the
\texttt{Future} has been assigned a value, the runnable is placed on the run
queue associated with the \texttt{Future} object. \textbf{\texttt{void
setRunQueue(RunQueue rq)}} void setRunQueue(RunQueue rq)sets the run queue
associated with a \texttt{Future} object. \textbf{\texttt{RunQueue
getRunQueue()}} RunQueue getRunQueue()gets the run queue associated with a
\texttt{Future} object. %\end{tabular}

 A chore can be scheduled for execution
upon a value being assigned to a \texttt{Future} . The call
\texttt{future.runDelayed(chore)} will schedule the chore for execution when the
\texttt{future} 's value is set. If \texttt{runDelayed} is called after the
\texttt{Future} has had a value assigned, the chore is immediately placed in a
run queue.

Each \texttt{Future} object contains a reference to the \texttt{RunQueue} object
that run-delayed chores will be placed in.

The constructor call \texttt{new Future()} creates a \texttt{Future} with no
value yet assigned, while \texttt{new Future(val)} creates a \texttt{Future}
with \texttt{val} assigned to its value. It may not be immediately obvious why
one might want to create a \texttt{Future} with a value assigned from the
beginning. It is useful when writing subroutines that arrange for a value to be
computed. The subroutine sometimes can perform the computation immediately and
sometimes will create threads or chores to perform the calculation. In either
case, it can return a \texttt{Future} object that the caller can look in when
the value is actually needed. It is a small programming convenience for the
subroutine to be able to supply the value when it creates the \texttt{Future} if
it already has it computed.

Method \texttt{getValue()} waits until a value has been assigned to the
\texttt{Future} and then returns it. It is the same as in \texttt{SimpleFuture}
. Similarly, method \texttt{isSet()} checks to see if a value has been assigned
to the \texttt{Future} yet.

Method \texttt{setValue(val)} assigns the object \texttt{val} to the
\texttt{Future} , notifies all waiting threads, and places all run-delayed
runnables in a run queue.

Each \texttt{Future} object has an associated run queue in which it will place
the run-delayed runnables. There is a run queue associated with class
\texttt{Future} that will be used if no other run queue is specified. Static
method \texttt{getClassRunQueue()} returns the run queue associated with the
\texttt{Future} class. This run queue starts off placing no limit on the number
of threads that can be created to run the runnables placed on it. You can assign
other limits to it.

Method call \texttt{f.setRunQueue(rq)} sets the run queue for a \texttt{Future}
object \texttt{f} to \texttt{rq} , and method \texttt{f.getRunQueue()} returns
\texttt{f} 's run queue. You would use \texttt{f.setRunQueue} to override the
default use of the \texttt{Future} class's run queue.

Method \texttt{f.runDelayed(r)} schedules the \texttt{Runnable} object
\texttt{r} to execute when \texttt{Future}

\texttt{f} has its value set. If it is called when the value has already been
set, \texttt{r} is immediately placed in \texttt{f's} run queue. If the value is
not yet set, \texttt{r} is stored in \texttt{f} and will be placed in the run
queue by \texttt{f.setValue()} .

\section{FutureFactory} When creating chore graphs, we will often need to create
futures that use a particular run queue. Rather than pass the run queue around
and assign it to every future we create, we can use a \texttt{FutureFactory}
object. A \texttt{FutureFactory} object will generate futures that reference a
particular run queue.

%\begin{tabular}

 Class \textbf{\texttt{FutureFactory}} FutureFactory
\textbf{\texttt{FutureFactory(RunQueue runQueue)}} FutureFactory(RunQueue
runQueue) \texttt{} creates a \texttt{FutureFactory} object. All the futures
created by the future factory will place run-delayed objects in the run queue
(i.e., unless their run queue is changed by \texttt{setRunQueue()} ).
\textbf{\texttt{Future make()}} Future make()creates a future.
\textbf{\texttt{RunQueue getRunQueue()}} RunQueue getRunQueue()gets the run
queue for a \texttt{FutureFactory} object. This can be used to set the
parameters of the run queue. \textbf{\texttt{void setRunQueue(RunQueue rq)}}
void setRunQueue(RunQueue rq)sets the run queue for a \texttt{FutureFactory}
object to \texttt{rq} . %\end{tabular} 

The constructor call \texttt{ff=new
FutureFactory(rq)} creates a future factory that will create futures that place
their run-delayed chores in \texttt{RunQueue}

\texttt{rq} . The call \texttt{f=ff.make()} has \texttt{FutureFactory}

\texttt{ff} make a new future \texttt{f} . Calling \texttt{f.runDelayed(r)} will
place \texttt{Runnable}

\texttt{r} in \texttt{RunQueue}

\texttt{rq} when a value has been assigned to \texttt{f} . Calls to
\texttt{ff.setRunQueue(rq)} and \texttt{ff.getRunQueue()} set and get,
respectively, the run queue that \texttt{FutureFactory}

\texttt{ff} will place in futures.

\section{Chore-programming Techniques} There are a number of programming
techniques for chores and ways to think about chore programming. We will present
them in this section and then show them in use in later examples.

There are two algorithms whose variants form many of our examples: vector
addition and Warshall's algorithm for transitive closure of boolean matrices
(first presented in \ref{../C/ParLoops.#id(14813)}[MISSING HREF] ). By vector
addition, we mean mathematical vectors, represented by arrays of
double-precision numbers, not \texttt{Vector} objects from the
\texttt{java.util} package.

\subsubsection{Job Jars} Job jars are one way to think of programming with
chores. A job jar is a queue of chores--a run queue. As a thread finishes one
chore, it can pick another chore from the job jar and execute it.

The term job jar comes from home economics: It is a jar full of slips of paper
naming chores to be done. When another chore is discovered, it is written on a
slip of paper and dropped in the job jar. When a member of the household has
some free time, he or she takes a slip of paper from the jar and does the chore.

Some chores may require that other chores be done, so part of a chore may be the
creation of more chores to put into the job jar. There may be dependencies among
chores that require that, at the completion of a chore, members of the household
decide whether it is now time to place another chore in the job jar or whether
the chore has some dependencies that are not yet fulfilled.

\subsubsection{Chore Graphs} In the previous chapter, we discussed chore graphs
as a design tool for laying out parallel computations in threads. If we are
programming using chores directly, the chore graphs are more than just a
conceptual tool. We have to create the chores in the chore graph as actual
objects and coordinate them.

What we will often do is write methods that, instead of directly computing the
actual result, will generate chore graphs to compute the result.

If the chore graph is not data dependent, we can write methods that generate the
entire graph. For example, a shell sort will execute passes that depend on the
size of the array to sort, but not on the contents. Given an array, we can
immediately generate chores to do the sorting. We will see this in the section
entitled \ref{ChoreGroups.#id(25959)}[MISSING HREF] .

On the other hand, if the chore graph is data dependent, we may have to have the
chores themselves generate more of the chore graph. For example,
\texttt{quicksort} creates subsorts whose bounds depend on the position that the
pivot element ends up in. That is data dependent. Therefore, a chore-based
approach to \texttt{quicksort} would have the chore that partitions a part of
the array then create chores to sort the subarrays. We will see this in the
section entitled \ref{ChoreGroups.#id(14351)}[MISSING HREF] .

\subsubsection{Macro Dataflow} Dataflow is a processor organization that can be
extended into a software design. The principle of dataflow is that operations
should be scheduled for execution when their operands become available. It is
the availability of the operands that triggers computation. Moreover, there is
no limit on how long the computation may wait before executing. This is unlike
the common von Neumann computer, where an instruction not only must not execute
before its operands are defined, but must not delay in executing past when an
operand has been reassigned. Moreover, in a von Neumann computer, instructions
are not scheduled according to the availability of their operands, but by
control flow. The control flow must be constructed with awareness of operand
availability.

There are two important concepts related to dataflow:

\begin{enumerate}

\item{Pure values. Unlike the conventional computer memory that may be
continually modified, dataflow values are assumed to be unchanging. This is what
allows the arbitrary delay in executing dataflow instructions.}

\item{Single assignment. An instance of a variable in a dataflow program may be
assigned a value only once. If it could be reassigned, there would be a window
in which the instructions using it could execute, rather than simply having to
wait for it to be assigned once. This means that each iteration of a loop and
each procedure call creates new instances of the variables that are assigned
values in it.}

\end{enumerate} Dataflow processors use the dataflow principle at the
individual-instruction level. Scalar operands such as integers, floats, and
booleans trigger individual instructions that compute scalar results.

Some early dataflow hardware designs were static dataflow. The machines
instructions themselves had space in them for the operands. The instructions
indicated where to store their results. When the second operand of a two-operand
instruction was stored, for example, the instruction with its operands was sent
to an execution unit. The code for such machines is not naturally reentrant: It
requires special hardware or software to allow code to be reused in loops.

Some dataflow hardware was designed as a distributed-memory parallel processor.
When instructions execute, they do not store their results directly in the
destination instructions, but send them out in tokens over a network that will
deliver them to the correct destination processor, instruction address, and
operand position (left or right).

A tagged-token dataflow hardware design got around the problem of providing
reentrant code by tagging the tokens not only with the destination processor,
instruction address, and operand position, but also with a subroutine activation
number and loop iteration count. Instead of operands being stored in the
instruction itself, a processor has a matching store, a kind of cache, where one
operand waits until the other operand arrives. When all the operands for an
instruction are present, the instruction is fetched, packed with its operands,
and sent off to an instruction execution unit.

Dataflow has obvious application to parallelism. When the operands become
available, an instruction can execute. The instruction needn't wait for flow of
control to come to it. The design principle works as well on a network or
distributed-memory machine as on a multiprocessor. And dataflow can be
implemented in software, as well as in hardware.

An obvious approach to software dataflow is to put operands in futures.
Instructions can get their operands from futures, being delayed until the future
has its value set. Then the instructions place their results in futures.

The problem is that this works poorly at the scalar level. The overhead would be
dozens or hundreds of machine instructions executed in synchronization and
thread dispatching for each instruction that does actual work.

Macro dataflow is a software dataflow implementation that tries to operate, to
the highest extent possible, on blocks of data, rather than individual scalars.
For example, a vector-matrix package could operate on entire vectors and rows of
matrices at a time. The cost of dispatching an operation would be amortized over
all the length of the vector, rather than a single scalar.

\subsection{Macro dataflow chore graphs} Macro dataflow executions can be
represented by chore graphs where the nodes are blocks of code and the edges
represent the data dependencies. You may imagine data flowing along the edges
from the tail of the edge where the data are produced to the head that uses
them. That means the edges will typically represent futures that are assigned
values by the chore at the tail of the edge and whose value is required by the
chore at the head.

It is probably aesthetically more pleasing to change the chore graph into a
bipartite graph where futures are also represented by nodes. (See Figure 7-1.) A
single edge will typically enter each node, from the chore that assigns it a
value. More than one edge entering a future would indicate that, for example,
the future is being set by both branches of an if statement, and we are
picturing both sides.

\includegraphics{figures/chores-1}

\subsection{Chore constructors} For our macro dataflow operations, we will
typically use classes whose constructors have the pattern

\texttt{ChoreClass(inputs, otherParameters, outputs)} The inputs and outputs
will typically be \texttt{Future} objects for macro dataflow, but the same
pattern can be used for other chore graphs.

\subsection{Fetching operands} The first problem we face in trying to implement
macro dataflow with chores is how to implement instructions that require more
than one operand. The idea behind chores is that chores will not block holding
onto a thread. What if a two-operand chore (a binary operator) fetches its left
operand and then is forced to wait for its right operand to become available? We
would expect the code to add two float arrays to be something like Example 7-1.

%\begin{tabular}
 
Example of blocking binary dataflow operation. 
\begin{verbatim}


class BinAddFloatArray implements Runnable \lbrack \end{verbatim}





\begin{verbatim}

 Future lopnd; Future ropnd; Future result; \end{verbatim}



\begin{verbatim}

 public BinAddFloatArray(Future lopnd, Future ropnd, Future
result)\lbrack \end{verbatim}



\begin{verbatim}

 this.lopnd = lopnd; this.ropnd = ropnd; this.result = result;
\end{verbatim}



\begin{verbatim}

 \rbrack \end{verbatim}



\begin{verbatim}

 public void run() \lbrack \end{verbatim}



\begin{verbatim}

 try\lbrack \end{verbatim}



\begin{verbatim}

 float[] left=(float[])lopnd.getValue(); \end{verbatim}



\begin{verbatim}

 float[] right=(float[])ropnd.getValue(); \end{verbatim}



\begin{verbatim}

 float[] sum=new float[left.length]; \end{verbatim}



\begin{verbatim}

 for (int i=0;i<sum.length;i++) sum[i]=left[i]+right[i];
\end{verbatim}



\begin{verbatim}

 result.setValue(sum); \end{verbatim}



\begin{verbatim}

 \rbrack catch (InterruptedException ex)\lbrack \rbrack
\end{verbatim}



\begin{verbatim}

 \rbrack \end{verbatim}



\begin{verbatim}

 \rbrack \end{verbatim}



	\begin{verbatim}



\end{verbatim}

 %\end{tabular} Won't the attempt to fetch the right operand block
its thread? Well, this code would. What we have to do is check that the operands
are available and give up the thread we are using if we have to wait. We would
code it something like Example 7-2.

%\begin{tabular}
 
Nonblocking binary dataflow operation. \begin{verbatim}

 class
BinAddFloatArray implements Runnable \lbrack \end{verbatim}



\begin{verbatim}

 Future lopnd; Future ropnd; Future result; \end{verbatim}



\begin{verbatim}

 public BinAddFloatArray( \end{verbatim}



\begin{verbatim}

 Future lopnd, Future ropnd, Future result)\lbrack
\end{verbatim}



\begin{verbatim}

 this.lopnd= lopnd; this.ropnd= ropnd; this.result= result;
\end{verbatim}



\begin{verbatim}

 \rbrack \end{verbatim}



\begin{verbatim}

 public void run() \lbrack \end{verbatim}



\begin{verbatim}

 try \lbrack \end{verbatim}



\begin{verbatim}

 if (!lopnd.isSet())\lbrack \end{verbatim}



\begin{verbatim}

 lopnd.runDelayed(this);return; \end{verbatim}



\begin{verbatim}

 \rbrack \end{verbatim}



\begin{verbatim}

 if (!ropnd.isSet())\lbrack \end{verbatim}



\begin{verbatim}

 ropnd.runDelayed(this);return; \end{verbatim}



\begin{verbatim}

 \rbrack \end{verbatim}



\begin{verbatim}

 float[] left=(float[])lopnd.getValue(); \end{verbatim}



\begin{verbatim}

 float[] right=(float[])ropnd.getValue(); \end{verbatim}



\begin{verbatim}

 float[] sum=new float[left.length]; \end{verbatim}



\begin{verbatim}

 for (int i=0;i<sum.length;i++) sum[i]=left[i]+right[i];
\end{verbatim}



\begin{verbatim}

 result.setValue(sum); \end{verbatim}



\begin{verbatim}

 \rbrack catch (InterruptedException ex)\lbrack \rbrack
\end{verbatim}



\begin{verbatim}

 \rbrack \end{verbatim}



\begin{verbatim}

 \rbrack \end{verbatim}



	\begin{verbatim}



\end{verbatim}

 %\end{tabular} The first lines of the \texttt{run()} method now
check to see if the operands are assigned yet. If an operand is not yet assigned
a value, they make this chore wait for it to be assigned by calling
\texttt{runDelayed(this)} and give up the chore's thread by returning. If the
right operand isn't available and the left one is, then the next time the chore
is started, it performs a redundant test, but that should be a relatively minor
overhead.

\subsubsection{Flow of Control} Even though our approach is to break computation
into independent chores, we will no doubt be thinking in terms of flow of
control. We will especially miss flow of control when there are a lot of small
operations to perform in sequence. Here are some techniques to implement flow of
control in chore graphs, including reusing the same class for more than one
chore.

\subsection{Changing run queues} One easy way to allow flow of control is to use
a thread instead of a chore. A thread is allowed to block between the chores it
is composed of, whereas a chore should run its body to completion. Since either
a chore or a thread may be packaged in a runnable and either may be placed in a
run queue, why not just run delay code for a thread on a future? The major
reason why not is that futures for chores will have run queues that limit the
maximum number of threads they can create at a time, and as remarked before,
this can lead to deadlock. After being run delayed on a future, a runnable is
associated with whatever run queue the future used to schedule it. This run
queue might have a limit on the number of threads it will create. If the
runnable actually is not a chore but a full thread, needing to block, for
example on \texttt{getValue()} from a future or a \texttt{down()} on a
semaphore, then it would reduce the number of threads for executing other
runnables on that run queue. If all the runnables holding threads created by
that run queue are blocked waiting for some actions that can only be performed
by runnables still enqueued on that queue and the queue is not allowed to create
any more threads, the system is deadlocked.

Therefore, a runnable may need change the run queue of the thread that is
executing it. It may need to use a thread from a run queue that has no limit on
the number of threads that can be created.

This can be accomplished with the code shown in \ref{chores.#id(65328)}[MISSING
HREF] . The intention is to change the run queue of the runnable to one with an
unlimited number of threads. The first time the runnable is scheduled, it
assigns itself to the unlimited run queue, handing itself over to a different
thread. When that thread starts running it, it will skip the hand-over and just
run.

%\begin{tabular}
 
Runnable changing run queues \begin{verbatim}



class ...\lbrack

	\end{verbatim}

 \begin{verbatim}



boolean firstEntry=true;

	\end{verbatim}

 \begin{verbatim}



... \end{verbatim}

 \begin{verbatim}



  public void run() \lbrack \end{verbatim}

 \begin{verbatim}



if (firstEntry) \lbrack

	\end{verbatim}

 \begin{verbatim}



firstEntry=false;

	\end{verbatim}

 \begin{verbatim}



unlimitedRunQueue.run(this);

	\end{verbatim}

 \begin{verbatim}



return;

	\end{verbatim}

 \begin{verbatim}



}

	\end{verbatim}

 \begin{verbatim}



    ... \end{verbatim}

 \begin{verbatim}



  } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular} \subsection{Switch statement} Another approach to
simulating flow of control is to put the code for several chores in a flow of
control in the same run method as cases in a \texttt{switch} statement. The
pattern is shown in \ref{chores.#id(47229)}[MISSING HREF] . Keep a program
counter, \texttt{pc} , field in the class. Use the program counter in the
\texttt{switch} statement to jump to the proper code. Naturally, each section of
code will assign the number of its successor to \texttt{pc} . This example shows
the handoff from the chore at \texttt{case 1} to the next chore at \texttt{case
2} . At the end of the first chore's processing, chore number two should run.
However, it needs to get the Object \texttt{v} out of \texttt{Future}

\texttt{f} , but it may not be assigned yet. So the last thing chore one does is
to set \texttt{pc} to 2, so that if it gives up the thread, chore two will
execute next. Then it tests to see if \texttt{f} has already had its value
assigned. If not, it runs itself delayed on the future, so when it runs again,
\texttt{f} will have been defined, and chore two will not block on the
\texttt{getValue()} call. If however, \texttt{f} does already have a value,
chore one just falls through into chore two.

%\begin{tabular}
 
Chores in a switch statement \begin{verbatim}



class ...\lbrack

	\end{verbatim}

 \begin{verbatim}



int pc=0; \end{verbatim}

 \begin{verbatim}



... \end{verbatim}

 \begin{verbatim}



  public void run() \lbrack \end{verbatim}

 \begin{verbatim}



    for (;;) try {switch (pc)\lbrack \end{verbatim}

 \begin{verbatim}



case 0: \end{verbatim}

 \begin{verbatim}



       ... \end{verbatim}

 \begin{verbatim}



case 1: \end{verbatim}

 \begin{verbatim}



       ...//body of chore 1 \end{verbatim}

 \begin{verbatim}



       pc=2; \end{verbatim}

 \begin{verbatim}



       if (!f.isSet()) \lbrack \end{verbatim}

 \begin{verbatim}



          f.runDelayed(this); \end{verbatim}

 \begin{verbatim}



          return; \end{verbatim}

 \begin{verbatim}



       } \end{verbatim}

 \begin{verbatim}



case 2: v=f.getValue(); \end{verbatim}

 \begin{verbatim}



       ... \end{verbatim}

 \begin{verbatim}



    } } catch (InterruptedException e){...} \end{verbatim}

 \begin{verbatim}



  } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular} The reason for the try statement is to placate the
Java compiler. Calling \texttt{getValue()} can theoretically throw an
\texttt{InterruptedException} , and the compiler will issue warnings if we don't
make provision for them.

\subsection{Create a continuation object} The method truest to the spirit of
chores is to have each chore schedule another chore object to execute the next
chore in sequence. This successor object can be dropped in a run queue or be run
delayed on a \texttt{Future} object. This approach has a lot in common with
continuation-passing style.

A continuation is a function that represents the rest of a program execution.
The idea behind it has been around since the early days of computing when people
were figuring out how to implement the language Algol 60. There was a question
over what features are really essential and what can be implemented in terms of
others. One researcher realized that you could get away with sequential
execution, \texttt{if} statements, procedures and procedure calls, but you
didn't need loops or procedure return. Suppose procedure A calls procedure B.
You would take the rest of the code in procedure A following a call of procedure
B and make it into a procedure of its own, a continuation procedure. The
continuation procedure says what you would do after the return from B. Then, the
continuation is passed to procedure B as an additional parameter. Now instead of
returning, procedure B ends by calling the continuation procedure it has been
passed, which will do what A was going to do after the return. You do this for
all procedures and all calls.

What about loops? A loop can be translated into a procedure that calls itself
recursively at the end.

Is this ever used? Yes. The language Scheme requires it. It is a common
implementation technique for functional languages. Tail-end calls, such as the
calls of continuations, can be efficiently implemented by loading parameters in
registers and jumping. Passing a continuation only requires creating a
functional object composed of an entry address and an environment.

Our use of this concept is to create an object for each chore. Each chore in the
sequence will schedule its successor. Sometimes, a chore will create an instance
of its continuation. Sometimes, we will create a chain of such objects before
starting the first of them running.

\subsection{Create a local continuation object.} A convenient form of
continuation object is a local object, declared using a nested class. The
contained, local object can access all the fields of the containing object.
Therefore, all the data fields the continuations need can be placed in the
surrounding object, and the continuation objects can just provide code in their
\texttt{run()} methods.

\section{Macro Dataflow Examples: Vector Addition} We will demonstrate a number
of macro dataflow techniques in this section using examples of vector addition.
By vector addition, we mean mathematical vectors, not \texttt{java.util} .Vector
objects. Vectors in \emph{n} -dimensional space are \emph{n} -tuples of real
numbers, which we represent by arrays of length \emph{n} of double-precision
floating-point numbers. Vector addition is performed by adding the corresponding
elements of the two vectors.

We have already shown two versions of vector addition in Examples 7-1 and 7-2. A
picture of our data structure is shown in Figure 7-2. In those examples, the
operations of waiting for and fetching operands, performing the addition, and
storing the results are all combined in one object and one \texttt{run()}
method. Here we will divide the operations into more than one class so that we
will have components that plug together. We have components to fetch operands,
to perform the operations, and to store the results. Using components makes it
easier to increase the functionality by adding additional, simple components
later.

\includegraphics{figures/chores-2} The plugs we use to connect components are
the interfaces \texttt{Op1} and \texttt{Op2} shown in
\ref{chores.#id(69132)}[MISSING HREF] . Both of them define a method
\texttt{op()} . For \texttt{Op1} , \texttt{op()} takes a single argument; for
\texttt{Op2} , it takes two. An object that implements either \texttt{Op1} or
\texttt{Op2} is a continuation object. It exists to continue some computation.
It says what is to be done next.

%\begin{tabular}
 
Op1 and Op2 interfaces \begin{verbatim}



interface Op1\lbrack

	\end{verbatim}

 \begin{verbatim}



public void op(Object opnd);

	\end{verbatim}

 \begin{verbatim}



}

	\end{verbatim}

 \begin{verbatim}



interface Op2\lbrack

	\end{verbatim}

 \begin{verbatim}



public void op(Object lopnd,Object ropnd);

	\end{verbatim}

 \begin{verbatim}



}

	\end{verbatim}

 %\end{tabular} 
	
\subsubsection{Continuations to Separate Operand Fetch from Operation} 

Our first example using \texttt{Op1} and
\texttt{Op2} continuations will fetch the two operands, add them, and
store the result in separate objects. This resembles the operand fetch,
execute, and store stages of a computer processor.

\includegraphics{figures/chores-3} The operand fetch is performed by class
\texttt{Binop1} (binary operation, version 1), pictured in Figure 7-3 and shown
in \ref{chores.#id(31567)}[MISSING HREF] . A \texttt{Binop1} object is created
with references to two futures for its left and right operands and an
\texttt{Op2} continuation to which to pass the operands once it has fetched
them. As shown before, it first tests the operand futures to see if the operands
are present. If they both are present, it fetches them and passes them to its
continuation. If either operand isn't present, \texttt{Binop1} run delays itself
on that operand's future. This will wait for the operand to become available
without holding on to a thread. When it is reawakened, it will start again
testing whether the operands are present. There is the extra cost of a redundant
test if it was waiting for the right operand to be available.

%\begin{tabular}
 
lass Binop1 \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class Binop1 implements Runnable\lbrack \end{verbatim}

 \begin{verbatim}



    Future lopnd,ropnd; \end{verbatim}

 \begin{verbatim}



    Op2 continuation; \end{verbatim}

 \begin{verbatim}



    public Binop1( \end{verbatim}

 \begin{verbatim}



		Future lopnd, \end{verbatim}

 \begin{verbatim}



		Future ropnd, \end{verbatim}

 \begin{verbatim}



		Op2 continuation)\lbrack \end{verbatim}

 \begin{verbatim}



	this.lopnd=lopnd; \end{verbatim}

 \begin{verbatim}



	this.ropnd=ropnd; \end{verbatim}

 \begin{verbatim}



	this.continuation=continuation; \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



    public void run() \lbrack \end{verbatim}

 \begin{verbatim}



	try { \end{verbatim}

 \begin{verbatim}



	    if (!lopnd.isSet()) {lopnd.runDelayed(this); return;} \end{verbatim}


	    \begin{verbatim}



	    if (!ropnd.isSet()) {ropnd.runDelayed(this); return;} \end{verbatim}


	    \begin{verbatim}



	    continuation.op(lopnd.getValue(),ropnd.getValue()); \end{verbatim}


	    \begin{verbatim}



	} catch (InterruptedException e){ \end{verbatim}

 \begin{verbatim}



	    continuation.op(e,e); \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular} The actual vector addition is done by class
\texttt{Vadd} , shown in \ref{chores.#id(98901)}[MISSING HREF] . \texttt{Vadd}
implements the \texttt{Op2} interface, so it has an \texttt{op()} method that is
called with the two vector operands. It is given a \texttt{Op1} continuation
when it is created. The continuation will be given the result of the vector
addition. It is up to the continuation to store the result or perhaps perform
more operations on it.

%\begin{tabular}
 
class Vadd \begin{verbatim}



class Vadd implements Op2{ \end{verbatim}

 \begin{verbatim}



    Op1 continuation; \end{verbatim}

 \begin{verbatim}



    Vadd(Op1 contin){continuation=contin;} \end{verbatim}

 \begin{verbatim}



    public void op(Object lopnd,Object ropnd){ \end{verbatim}

 \begin{verbatim}



	    double [] x,y,z; \end{verbatim}

 \begin{verbatim}



	    if (lopnd instanceof Exception) \end{verbatim}

 \begin{verbatim}



		    continuation.op(lopnd); \end{verbatim}

 \begin{verbatim}



	    if (ropnd instanceof Exception) \end{verbatim}

 \begin{verbatim}



		    continuation.op(ropnd); \end{verbatim}

 \begin{verbatim}



	    try { \end{verbatim}

 \begin{verbatim}



		    x=(double[])lopnd; \end{verbatim}

 \begin{verbatim}



		    y=(double[])ropnd; \end{verbatim}

 \begin{verbatim}



		    z=new double[x.length]; \end{verbatim}

 \begin{verbatim}



		    for (int i=0;i<z.length;++i) \end{verbatim}

 \begin{verbatim}



			    z[i]=x[i]+y[i]; \end{verbatim}

 \begin{verbatim}



		    continuation.op(z); \end{verbatim}

 \begin{verbatim}



	    } catch (Exception e){continuation.op(e);} \end{verbatim}


	    \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular} Because the \texttt{Op1} and \texttt{Op2}
interfaces are used for a variety of operations, they cannot be specific about
what kinds of operands are being passed. They declare their parameters of type
\texttt{Object} and leave it up to the object implementing the interface to cast
objects to the specific type required. Thus, \texttt{Vadd} has to cast its left
and right operands into arrays of doubles.

The result of the vector addition needs to be stored in a \texttt{future} for
other uses later. Clearly there has to be some operation implementing the
\texttt{Op1} interface that can store its operand in a \texttt{future} . We
allow a \texttt{future} to do this itself. Class \texttt{DFFuture1} (dataflow
future, version 1), shown in \ref{chores.#id(15547)}[MISSING HREF] , extends
\texttt{Future} and implements \texttt{Op1} . Its \texttt{op()} method simply
stores its operand.

%\begin{tabular}
 
class DFFuture1 \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class DFFuture1 extends Future implements Op1{ \end{verbatim}

 \begin{verbatim}



	public void op(Object opnd){ \end{verbatim}

 \begin{verbatim}



		setValue(opnd); \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular} Class \texttt{TestVadd1} , shown in
\ref{chores.#id(97765)}[MISSING HREF] , shows \texttt{Binop1} , \texttt{Vadd} ,
and \texttt{DFFuture1} in action. The significant line is

%\begin{tabular}
 
TestVadd1 \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class TestVadd1 { \end{verbatim}

 \begin{verbatim}



    public static void main(String[] args) \end{verbatim}

 \begin{verbatim}



		throws InterruptedException{ \end{verbatim}

 \begin{verbatim}



	    double [] x={1.0,2.0,3.0}; \end{verbatim}

 \begin{verbatim}



	    double [] y={4.0,5.0,6.0}; \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f1=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f2=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f3=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    f1.runDelayed(new Binop1(f1,f2,new Vadd(f3))); \end{verbatim}


	    \begin{verbatim}



	    f1.setValue(x); \end{verbatim}

 \begin{verbatim}



	    f2.setValue(y); \end{verbatim}

 \begin{verbatim}



	    double [] z=(double[])f3.getValue(); \end{verbatim}

 \begin{verbatim}



	    for (int i=0;i<z.length;++i) \end{verbatim}

 \begin{verbatim}



		    System.out.print(z[i]+" "); \end{verbatim}

 \begin{verbatim}



	    System.out.println(); \end{verbatim}

 \begin{verbatim}



	    Future.getClassRunQueue().setMaxThreadsWaiting(0); \end{verbatim}


	    \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}


%\
} \end{verbatim}

 %\end{tabular}

\begin{verbatim}



	f1.runDelayed(new Binop1(f1,f2,new Vadd(f3))); \end{verbatim}

 The
	operands will be found in futures \texttt{f1} and \texttt{f2} . The
	result will be placed in \texttt{DFFuture1}

\texttt{f3} . The \texttt{Vadd} object is given \texttt{f3} as its continuation.
The operands are fetched by \texttt{Binop1} and passed to the \texttt{Vadd}
object. The \texttt{Binop1} object could have been placed on a run queue, but
for efficiency, it was run delayed on its left operand. It won't be able to run
until both operands are present anyway, so it might as well be delayed until at
least one of them is present.

\subsubsection{Static Dataflow Style and Storing Operands in Instructions} Our
second version of vector addition will use a static dataflow style. We will
store operands in the dataflow instructions themselves, and when all the
operands are present, we will execute the instruction.

For the static dataflow, we introduce the interface \texttt{StoreOp} , shown in
\ref{chores.#id(85900)}[MISSING HREF] . Interface \texttt{StoreOp} declares a
single method \texttt{store(int i, Object value)} . Method \texttt{store()} will
place the value at the position \texttt{i} in the object implementing the
interface.

%\begin{tabular}
 
interface StoreOp \begin{verbatim}



interface StoreOp{ \end{verbatim}

 \begin{verbatim}



	public void store(int i,Object value); \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 We now can create a static-dataflow version of
\texttt{Binop} , class \texttt{Binop2} , shown in
\ref{chores.#id(45919)}[MISSING HREF] . \texttt{Binop2} (binary operation,
version 2) implements the \texttt{StoreOp} interface. It does not implement the
\texttt{Runnable} interface, since it is no longer responsible for fetching its
own operands. When a \texttt{Binop2} object is created, it is given an
\texttt{Op2} continuation object, which it is to call with the two operands
stored in it-- \texttt{lopnd} and \texttt{ropnd} . Initially, these operands
have no value. Conceptually, the left operand, \texttt{lopnd} , has position
zero, and \texttt{ropnd} has position one. Method store(int i,Object value) will
place the value in \texttt{lopnd} if \texttt{i} is zero and the \texttt{ropnd}
field if \texttt{i} is one (actually, anything other than zero). The
\texttt{Binop2} object keeps track of how many operands it still needs in its
\texttt{needed} field.

%\begin{tabular}
 
class Binop2 \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class Binop2 implements StoreOp{ \end{verbatim}

 \begin{verbatim}



    Object lopnd,ropnd; \end{verbatim}

 \begin{verbatim}



    Op2 continuation; \end{verbatim}

 \begin{verbatim}



    int needed=2; \end{verbatim}

 \begin{verbatim}



    public Binop2(Op2 continuation){ \end{verbatim}

 \begin{verbatim}



	        this.continuation=continuation; \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



    public void store(int i,Object value){ \end{verbatim}

 \begin{verbatim}



	       if (i==0) lopnd=value; \end{verbatim}

 \begin{verbatim}



	        else ropnd=value; \end{verbatim}

 \begin{verbatim}



	       if (--needed==0) continuation.op(lopnd,ropnd); \end{verbatim}


	       \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 
%\begin{tabular}
 
class Fetch \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class Fetch implements Runnable { \end{verbatim}

 \begin{verbatim}



    Future src; \end{verbatim}

 \begin{verbatim}



    Op1 continuation; \end{verbatim}

 \begin{verbatim}



    public Fetch(Future src, Op1 continuation){ \end{verbatim}

 \begin{verbatim}



	         this.src=src; \end{verbatim}

 \begin{verbatim}



	         this.continuation=continuation; \end{verbatim}

 \begin{verbatim}



        } \end{verbatim}

 \begin{verbatim}



        public void run() { \end{verbatim}

 \begin{verbatim}



	    try { \end{verbatim}

 \begin{verbatim}



	        if (!src.isSet()) src.runDelayed(this); \end{verbatim}


	        \begin{verbatim}



	        continuation.op(src.getValue()); \end{verbatim}

 \begin{verbatim}



	    } catch(InterruptedException e) { \end{verbatim}

 \begin{verbatim}



	        continuation.op(e); \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 %\begin{tabular} 

class Store \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class Store implements Op1{ \end{verbatim}

 \begin{verbatim}



    StoreOp dst; \end{verbatim}

 \begin{verbatim}



    int pos; \end{verbatim}

 \begin{verbatim}



    public Store(StoreOp dst,int pos){ \end{verbatim}

 \begin{verbatim}



	    this.dst=dst; \end{verbatim}

 \begin{verbatim}



	    this.pos=pos; \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



    public void op(Object value){ \end{verbatim}

 \begin{verbatim}



	    dst.store(pos,value); \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 Class \texttt{Fetch} , shown in
\ref{chores.#id(30107)}[MISSING HREF] , fetches operands from futures. It will
pass the value it fetches to an \texttt{Op1} object. Class \texttt{Store,} shown
in \ref{chores.#id(13294)}[MISSING HREF] , is used to store the operands in
\texttt{Binop2} binary dataflow instructions. It implements the \texttt{Op1}
interface. It is created with a \texttt{StoreOp} destination \texttt{dst} and an
index \texttt{pos} . When it's \texttt{op()} method is called, it stores the
operand at the specified index in the destination.

\texttt{TestVadd2} , shown in \ref{chores.#id(32965)}[MISSING HREF] , shows
\texttt{Binop2} , \texttt{Fetch} , and \texttt{Store} in action. The most
significant lines are

%\begin{tabular} 

class TestVadd2 \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class TestVadd2 { \end{verbatim}

 \begin{verbatim}



    public static void main(String[] args) \end{verbatim}

 \begin{verbatim}



		throws InterruptedException{ \end{verbatim}

 \begin{verbatim}



	    double [] x={1.0,2.0,3.0}; \end{verbatim}

 \begin{verbatim}



	    double [] y={4.0,5.0,6.0}; \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f1=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f2=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f3=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    Binop2 bop=new Binop2(new Vadd(f3)); \end{verbatim}

 \begin{verbatim}



	    f1.runDelayed(new Fetch(f1,new Store(bop,0))); \end{verbatim}


	    \begin{verbatim}



	    f2.runDelayed(new Fetch(f2,new Store(bop,1))); \end{verbatim}


	    \begin{verbatim}



	    f1.setValue(x); \end{verbatim}

 \begin{verbatim}



	    f2.setValue(y); \end{verbatim}

 \begin{verbatim}



	    double [] z=(double[])f3.getValue(); \end{verbatim}

 \begin{verbatim}



	    for (int i=0;i<z.length;++i) \end{verbatim}

 \begin{verbatim}



		    System.out.print(z[i]+" "); \end{verbatim}

 \begin{verbatim}



	    System.out.println(); \end{verbatim}

 \begin{verbatim}



	    Future.getClassRunQueue().setMaxThreadsWaiting(0); \end{verbatim}


	    \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 \begin{verbatim}



	Binop2 bop=new Binop2(new Vadd(f3)); \end{verbatim}

 \begin{verbatim}



	f1.runDelayed(new Fetch(f1,new Store(bop,0))); \end{verbatim}


	\begin{verbatim}



	f2.runDelayed(new Fetch(f2,new Store(bop,1))); \end{verbatim}

 The first
	line creates

\begin{enumerate}

\item{a vector add that will store its result in future f3 and}

\item{a binary operation that will pass two operands to the vector addition when
the operands become available.}

\end{enumerate} The second line creates a Fetch-Store pipe to fetch the left
operand and store it in the binary operation. The third line fetches the right
operand. Both lines are run delayed on the futures from which they fetch their
operands.

\subsubsection{Fetching in continuations} The third version of vector addition
fetches the right operand in a continuation. Class \texttt{TestVadd3} , shown in
\ref{chores.#id(99281)}[MISSING HREF] , shows the code to test out the idea. The
significant code is as follows:

\begin{verbatim}



	Fetch operation= \end{verbatim}

 \begin{verbatim}



		new Fetch(f1, \end{verbatim}

 \begin{verbatim}



			new Fetch2nd(f2, \end{verbatim}

 \begin{verbatim}



				new Vadd(f3))); \end{verbatim}

 The Fetch
				operation fetches the left operand and passes it
				to the \texttt{Fetch2nd} operation, which
				fetches the right operand and passes the pair of
				them to the \texttt{Vadd} instruction.

%\begin{tabular} 

class TestVadd3 \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class TestVadd3 { \end{verbatim}

 \begin{verbatim}



    public static void main(String[] args) \end{verbatim}

 \begin{verbatim}



		throws InterruptedException{ \end{verbatim}

 \begin{verbatim}



	    double [] x={1.0,2.0,3.0}; \end{verbatim}

 \begin{verbatim}



	    double [] y={4.0,5.0,6.0}; \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f1=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f2=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    DFFuture1 f3=new DFFuture1(); \end{verbatim}

 \begin{verbatim}



	    Fetch operation= \end{verbatim}

 \begin{verbatim}



		    new Fetch(f1, \end{verbatim}

 \begin{verbatim}



			    new Fetch2nd(f2, \end{verbatim}

 \begin{verbatim}



				     new Vadd(f3))); \end{verbatim}


				     \begin{verbatim}



	    f1.runDelayed(operation); \end{verbatim}

 \begin{verbatim}



	    f1.setValue(x); \end{verbatim}

 \begin{verbatim}



	    f2.setValue(y); \end{verbatim}

 \begin{verbatim}



	    double [] z=(double[])f3.getValue(); \end{verbatim}

 \begin{verbatim}



	    for (int i=0;i<z.length;++i) \end{verbatim}

 \begin{verbatim}



		    System.out.print(z[i]+" "); \end{verbatim}

 \begin{verbatim}



	    System.out.println(); \end{verbatim}

 \begin{verbatim}



	    Future.getClassRunQueue().setMaxThreadsWaiting(0); \end{verbatim}


	    \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 Class \texttt{Fetch2nd} , shown in
\ref{chores.#id(35963)}[MISSING HREF] , implements both \texttt{Op1} and
\texttt{Runnable} . It is created with \texttt{Future}

\texttt{src} and an \texttt{Op2}

\texttt{continuation} . When its \texttt{op()} method is called with the left
operand, it saves it in field \texttt{lopnd} and then executes its
\texttt{run()} method. The \texttt{run()} method tries to fetch the right
operand from \texttt{src} . If the \texttt{src}

\texttt{future} doesn't have a value yet, it run delays itself on \texttt{src}
to try again when \texttt{src} has been given a value. When \texttt{src} does
have a value, \texttt{Fetch2nd} passes the left operand it got from its
\texttt{op()} method and the right operand it got from \texttt{src} to its
continuation's \texttt{op()} method.

%\begin{tabular} 

class Fetch2nd \begin{verbatim}



import com.toolsofcomputing.thread.*; \end{verbatim}

 \begin{verbatim}



class Fetch2nd implements Runnable, Op1{ \end{verbatim}

 \begin{verbatim}



    Object lopnd; \end{verbatim}

 \begin{verbatim}



    Future src; \end{verbatim}

 \begin{verbatim}



    Op2 continuation; \end{verbatim}

 \begin{verbatim}



    public Fetch2nd(Future src,Op2 continuation){ \end{verbatim}


    \begin{verbatim}



	    this.src=src; \end{verbatim}

 \begin{verbatim}



	    this.continuation=continuation; \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



    public void op(Object value){ \end{verbatim}

 \begin{verbatim}



	    lopnd=value; \end{verbatim}

 \begin{verbatim}



	    run(); \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



    public void run() { \end{verbatim}

 \begin{verbatim}



	    try { \end{verbatim}

 \begin{verbatim}



	        if (!src.isSet()) src.runDelayed(this); \end{verbatim}


	        \begin{verbatim}



	        continuation.op(lopnd,src.getValue()); \end{verbatim}


	        \begin{verbatim}



	    } catch(InterruptedException e) { \end{verbatim}

 \begin{verbatim}



	        continuation.op(lopnd,e); \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 Version 3 has a bit of cleanliness compared with
the two other versions. Unlike the first version's \texttt{Binop1} object, it
doesn't have to check the left operand more than once. \texttt{Binop1} will
check it's left operand again, even if it was run delayed on its right operand.
Unlike \texttt{Binop2} , version 3 doesn't have to have the extra four objects
to fetch the two operands and store them in the \texttt{Binop2} object. The cost
is simply one object per operand, one for the operation, and one more to dispose
of the result.

\section{Chore Examples: Warshall's Algorithm} We presented Warshall's algorithm
for transitive closure in \ref{../C/ParLoops.#id(66607)}[MISSING HREF] . Even
there, we used an optimization of it, as shown in
\ref{chores.#id(66607)}[MISSING HREF] . In the original, the code within the
three loops is

%\begin{tabular}

Warshall's algorithm \begin{verbatim}



for (k=0; k<N; k++) \end{verbatim}

 \begin{verbatim}



    for (i=0; i<N; i++) \end{verbatim}

 \begin{verbatim}



        if (A[i][k]) \end{verbatim}

 \begin{verbatim}



            for (j=0; j<N; j++) \end{verbatim}

 \begin{verbatim}



                A[i][j] = A[i][j] || A[k][j] ; \end{verbatim}

 %\end{tabular}


                A[i][j] = A[i][j] || (A[i][k] and A[k][j]);

where we conjoin the \texttt{j} th position of row \texttt{k} into the
\texttt{j} th position of row \texttt{i} if \texttt{A[i][k]} is true. Since
\texttt{A[i][k]} will be the same for all values of \texttt{j} , we remove the
test to outside the inner \texttt{j} loop. We test to see if row \texttt{i} has
a true value in the \texttt{k} th position, \texttt{A[i][k]} . If so, we conjoin
into it the \texttt{k} th row. Otherwise, we leave the \texttt{i} th row
unaltered.

In our code in this section, the middle \texttt{i} loop has vanished. We operate
in parallel on the rows. Each row, in fact, is processed by a separate object,
each of which has its own copy of index \texttt{i} . The \texttt{i} loop has
vanished into parallel chains of chores.

We will show four versions of Warshall's algorithm using chores. The first,
\texttt{WarshallDF1} , uses dataflow techniques. The other three,
\texttt{WarshallC1} through \texttt{WarshallC3} , use chores, but they modify
the rows in place, which violates the dataflow spirit by making the computations
timing dependent.

\subsubsection{WarshallDF1 and Warshall's Algorithm in Dataflow} Class
\texttt{WarshallDF1} is a dataflow approach to Warshall's algorithm.
\ref{chores.#id(74432)}[MISSING HREF] shows the global structure of
\texttt{WarshallDF1} . When we create a copy of \texttt{WarshallDF1} , we
specify the number of threads it is to use in computing the transitive closure
of a boolean matrix.

%\begin{tabular} 

WarshallDF1 structure \begin{verbatim}



class WarshallDF1{ \end{verbatim}

 \begin{verbatim}



 int numThreads; \end{verbatim}

 \begin{verbatim}



 public WarshallDF1(int numThreads){ \end{verbatim}

 \begin{verbatim}



	this.numThreads=numThreads; \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



 private class RowUpdate implements Runnable { \end{verbatim}

 \begin{verbatim}



... \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 \begin{verbatim}



 public boolean[][] closure(boolean[][] a) { \end{verbatim}

 \begin{verbatim}



... \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 When we wish to compute the transitive closure
of a matrix, we pass the matrix to method \texttt{closure()} , which will return
a new matrix that is the transitive closure of the input matrix. Method
\texttt{closure()} builds a dataflow graph to compute the transitive closure. It
does the updates in stages, as pictured in \ref{Chores.#id(64735)}[MISSING HREF]
. For an \includegraphics{figures/chores-4} boolean matrix, there are N stages
in the dataflow graph. A row is updated as a unit by a chore. The chores are
instances of the \texttt{RowUpdate} class.

\includegraphics{figures/chores-5} Method \texttt{closure()} , shown in
\ref{chores.#id(16274)}[MISSING HREF] , builds the stages using two arrays of
futures, the source array \texttt{src} , and the destination array, \texttt{dst}
. The futures in these arrays will have rows assigned to them. To create the
futures, \texttt{closure()} creates a future factory \texttt{ff} that uses a run
queue that is restricted to create no more than the desired number of threads at
a time. The original \texttt{src} array is initialized to futures, which are
themselves initialized to the values of the rows of the input array.

%\begin{tabular} 

Method closure() of WarshallDF1 \begin{verbatim}



 public boolean[][] closure(boolean[][] a) { \end{verbatim}

 \begin{verbatim}



	int i,j,k; \end{verbatim}

 \begin{verbatim}



	RunQueue rq=new RunQueue(numThreads); \end{verbatim}

 \begin{verbatim}



	 ff=new (rq); \end{verbatim}

 \begin{verbatim}



	Future[] srcRows=new Future[a.length]; \end{verbatim}

 \begin{verbatim}



	for (i=0;i<srcRows.length;++i) { \end{verbatim}

 \begin{verbatim}



		srcRows[i]=ff.make(); \end{verbatim}

 \begin{verbatim}



		srcRows[i].setValue(a[i]); \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	for (k=0;k<a.length;k++) { \end{verbatim}

 \begin{verbatim}



		Future[] dstRows=new Future[a.length]; \end{verbatim}


		\begin{verbatim}



		for (i=0;i<a.length;i++) { \end{verbatim}

 \begin{verbatim}



			if (i==k) dstRows[i]=srcRows[i]; \end{verbatim}


			\begin{verbatim}



			else { \end{verbatim}

 \begin{verbatim}



				dstRows[i]=ff.make(); \end{verbatim}


				\begin{verbatim}



				srcRows[i].runDelayed( \end{verbatim}


				\begin{verbatim}



					new RowUpdate( \end{verbatim}


					\begin{verbatim}



						srcRows[i], \end{verbatim}


						\begin{verbatim}



						srcRows[k], \end{verbatim}


						\begin{verbatim}



						k, \end{verbatim}


						\begin{verbatim}



						dstRows[i]) ); \end{verbatim}


						\begin{verbatim}



			} \end{verbatim}

 \begin{verbatim}



		} \end{verbatim}

 \begin{verbatim}



		srcRows = dstRows; \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	boolean[][] result=new boolean[a.length][]; \end{verbatim}


	\begin{verbatim}



	try { \end{verbatim}

 \begin{verbatim}



	    for (i=0;i<a.length;i++) \end{verbatim}

 \begin{verbatim}



		    result[i]=(boolean[])srcRows[i].getValue(); \end{verbatim}


		    \begin{verbatim}



	} catch (InterruptedException ex){} \end{verbatim}

 \begin{verbatim}



	rq.setMaxThreadsWaiting(0); \end{verbatim}

 \begin{verbatim}



	return result; \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 The stages are generated by a loop that creates an
array of destination futures. This loop is the translation of the outer
\texttt{k} loop of Warshall's algorithm. Except for the \texttt{k} th row, all
rows \texttt{i} from the stage \texttt{k} to stage \texttt{k+1} are updated by
creating

\begin{enumerate}

\item{a destination future and}

\item{a RowUpdate operation that will conditionally disjoin it with the k th
source row.}

\end{enumerate} The \texttt{k} th row would not be changed by a
\texttt{RowUpdate} , so we omit any operation by simply reusing the \texttt{k}
th source future as the \texttt{k} th destination future, and not creating any
update operation.

\texttt{RowUpdate} , shown in \ref{chores.#id(21965)}[MISSING HREF] , is created
with four parameters:

%\begin{tabular} 

Class RowUpdate of WarshallDF1 \begin{verbatim}



 private class RowUpdate implements Runnable { \end{verbatim}

 \begin{verbatim}



	boolean[] row=null; \end{verbatim}

 \begin{verbatim}



	Future myRow; \end{verbatim}

 \begin{verbatim}



	int k; \end{verbatim}

 \begin{verbatim}



	Future kthRow; \end{verbatim}

 \begin{verbatim}



	Future resultRow; \end{verbatim}

 \begin{verbatim}



	int j; \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	RowUpdate( Future myRow, \end{verbatim}

 \begin{verbatim}



	     Future kthRow, \end{verbatim}

 \begin{verbatim}



	     int k, \end{verbatim}

 \begin{verbatim}



	     Future resultRow){ \end{verbatim}

 \begin{verbatim}



		this.myRow=myRow; \end{verbatim}

 \begin{verbatim}



		this.k=k; \end{verbatim}

 \begin{verbatim}



		this.kthRow=kthRow; \end{verbatim}

 \begin{verbatim}



		this.resultRow=resultRow; \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	public void run() { \end{verbatim}

 \begin{verbatim}



	 try { \end{verbatim}

 \begin{verbatim}



	    if (row==null) { \end{verbatim}

 \begin{verbatim}



		    if (!myRow.isSet()){ \end{verbatim}

 \begin{verbatim}



			    myRow.runDelayed(this); \end{verbatim}


			    \begin{verbatim}



			    return; \end{verbatim}

 \begin{verbatim}



		    } \end{verbatim}

 \begin{verbatim}



	    	    row = (boolean[])myRow.getValue(); \end{verbatim}


	    	    \begin{verbatim}



	    	    if (!row[k]) { \end{verbatim}

 \begin{verbatim}



			    resultRow.setValue(row); \end{verbatim}


			    \begin{verbatim}



			    return; \end{verbatim}

 \begin{verbatim}



	    	    } \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    if (!kthRow.isSet()) { \end{verbatim}

 \begin{verbatim}



		    kthRow.runDelayed(this); \end{verbatim}

 \begin{verbatim}



		    return; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    boolean[] row_k = (boolean[])kthRow.getValue(); \end{verbatim}


	    \begin{verbatim}



	    boolean[] result=new boolean[row.length]; \end{verbatim}


	    \begin{verbatim}



	    for(j=0;j<row.length;j++) { \end{verbatim}

 \begin{verbatim}



		    result[j] = row[j] | row_k[j]; \end{verbatim}


		    \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    resultRow.setValue(result); \end{verbatim}

 \begin{verbatim}



	 } catch (InterruptedException ex){} \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 %\end{tabular}

 \begin{enumerate}

\item{myRow: The future from which it will read the row it is updating.}

\item{kthRow: The future from which it will read the k th row, if necessary.}

\item{k: The step number.}

\item{resultRow: The future into which it will place the row it is updating.}

\end{enumerate} If \texttt{row[k]} is true, \texttt{RowUpdate} must fetch
\texttt{kthRow} and disjoin it with \texttt{row} . If \texttt{row[k]} is false,
it can ignore the \texttt{k} th row. Therefore, \texttt{RowUpdate} 's
\texttt{run()} method first fetches \texttt{row} , the contents of future
\texttt{myRow} , run delaying itself on \texttt{myRow} if necessary. Then, it
checks \texttt{row[k]} to see if it must also fetch \texttt{kthRow} 's contents.
If it doesn't need to fetch \texttt{kthRow} 's contents, it just stores
\texttt{row} into the \texttt{resultRow} future.

If it must fetch the \texttt{k} th row, it checks to see if the \texttt{kthRow}
future is already set. If it is set, \texttt{RowUpdate} can fetch its contents
and compute the result immediately; otherwise, it must run delay itself on the
\texttt{future} . When it is reawakened, it checks to see if it already has the
row from the \texttt{Future myRow} , and discovering it has, it doesn't fetch it
again.

The performance of \texttt{WarshallDF1} is shown in
\ref{Chores.#id(20183)}[MISSING HREF] . It was run on a dual-processor machine
having a Java implementation with kernel threads. In this experiment, more
threads performed better than fewer threads, at least up to five threads.

\includegraphics{figures/chores-6}

\subsubsection{WarshallC1 through WarshallC3 : Chores, But not Dataflow} The
principle behind examples \texttt{WarshallC1} through \texttt{WarshallC3} is to
use runnable objects for the calculation, but not dataflow. An \texttt{instance}
of a class is created for calculating each row of the result. These update their
rows communicating only when necessary.

Warshall's algorithm has three nested loops. The outer \texttt{k} loop takes the
algorithm through \emph{N} steps. The middle \texttt{i} loop selects a row, and
the inner \texttt{j} loop updates the row. The inner loops can be run in
parallel.

In these versions of Warshall's algorithm, the \texttt{i} loops are removed.
Each row is processed by its own runnable object. Each object keeps track of its
copy of variable \texttt{k} and has an inner \texttt{j} loop.

A runnable object only has to communicate when either

\begin{enumerate}

\item{It has the k th row and the step number is k . It has to provide its row
to all other runnables that need it.}

\item{In step k , this object's row[ k ] is true. This object must read the
value of the k th row at step k to disjoin into its own row.}

\end{enumerate} The communication is accomplished as follows: There is a shared
array of \emph{N} futures, \texttt{row\_k\_step\_k} . Each of the runnables
keeps track of the step number it is processing. (That is, each of them keeps
its own copy of the \texttt{k} value.) On step \texttt{k} , the runnable with
the \texttt{k} th row stores a copy of its row in the \texttt{k} th element of
the shared array \texttt{row\_k\_step\_k} . Similarly, on the \texttt{k} th
step, any runnable with \texttt{row[k]}

\texttt{true} will get the value of the \texttt{k} th row at
\texttt{row\_k\_step\_k[k]} .

The runnables do not have to run lock stepped. They can have their own separate,
unequal values of \texttt{k} . They are only synchronized when they need to
fetch values out of \texttt{row\_k\_step\_k} .

Here is a quick preview of the variants of Warshall's algorithm:

\begin{itemize}

\item{WarshallC1 is the baseline Warshall's algorithm. It uses a thread for each
row, so it is not chore based. The other versions can be considered variants of
this algorithm. The problem in translating to chores is that the thread can be
blocked in the middle while waiting at a getValue() to fetch the value out of a
future . This getValue() call marks a chore boundry in the thread.}

\item{WarshallC2 uses one runnable object to handle each row. The run() method
consists of several chores. It uses the trick of having a switch and a pc field
to allow each entry of run() to execute the correct chore.}

\item{WarshallC3 uses several objects to handle each row. All the data for
handling a row are kept in one object. The code for different chores is kept in
subobjects declared in inner classes. Each of these inner classes provides code
for a continuation chore.}

\end{itemize}

\subsection{WarshallC1} The overall structure of \texttt{WarshallC1} is given in
\ref{chores.#id(29444)}[MISSING HREF] . To perform transitive closures, you
create an instance of a \texttt{WarshallC1} object and call its \texttt{closure}
method.

%\begin{tabular} 

WarshallC1 overall structure \begin{verbatim}



class WarshallC1{ \end{verbatim}

 \begin{verbatim}



 private class Row extends Thread{...} \end{verbatim}

 \begin{verbatim}



 public boolean[][] closure(boolean[][] a) {...} \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 The \texttt{closure()} method, shown in
\ref{chores.#id(46272)}[MISSING HREF] , manages the computation of the
transitive closure. The actual work is performed by the thread class
\texttt{Row} . There will be one thread for each row of the matrix. Method
\texttt{closure()} performs the following operations:

%\begin{tabular} 

Method closure() of WarshallC1 \begin{verbatim}



 public boolean[][] closure(boolean[][] a) { \end{verbatim}

 \begin{verbatim}



	int i; \end{verbatim}

 \begin{verbatim}



	Future[] kthRows=new Future[a.length]; \end{verbatim}

 \begin{verbatim}



	for (i=0;i<kthRows.length;++i) \end{verbatim}

 \begin{verbatim}



		kthRows[i]=new Future(); \end{verbatim}

 \begin{verbatim}



	Accumulator done=new Accumulator(a.length, \end{verbatim}


	\begin{verbatim}



		new boolean[a.length][]); \end{verbatim}

 \begin{verbatim}



	for (i=0;i<a.length;i++) { \end{verbatim}

 \begin{verbatim}



		new Row((boolean[])a[i].clone(),i,kthRows,done).start();
		\end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	boolean[][] result=null; \end{verbatim}

 \begin{verbatim}



	try { \end{verbatim}

 \begin{verbatim}



	    result=(boolean[][])done.getFuture().getValue(); \end{verbatim}


	    \begin{verbatim}



	} catch (InterruptedException ex){} \end{verbatim}

 \begin{verbatim}



	return result; \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 \begin{enumerate}

\item{Since the algorithm operates in N steps and during each step k, the rows
of the matrix are updated by disjoining them with the k th row, closure()
creates an array of Future objects, kthRows , to hold each of the k th rows to
be used during the k th step of computing the other rows.}

\item{To be consistent with WarshallDF1 , closure() will return a boolean matrix
as its value. Each of the Row threads will produce one row of the result. The
Row threads will place their rows in an array. The closure method creates an
accumulator , done , for the row threads to use in producing their parts of the
result. The data in the accumulator contains a boolean matrix with the rows
empty. The row threads will place their rows in the matrix and signal their
completion. Method closure() will wait for the completion of the computation by
waiting for the accumulator to yield its value.}

\item{Method closure() starts the threads to calculate the rows. Each Row thread
is given its row to work on. These rows are cloned from the input array to be
consistent with WarshallDF1 . Normally, transitive closure operations are done
in place, modifying the input array. Each row object is also told its row
number, the array of futures kthRows that will hold the rows needed during the k
th step, and the done accumulator that it will place its row into and signal
when it completes.}

\end{enumerate} Local class \texttt{Row} , shown in
\ref{chores.#id(35645)}[MISSING HREF] , performs the actual computation of the
rows of the transitive closure. The class is created with the following
parameters:

%\begin{tabular} 

Row class of WarshallC1 \begin{verbatim}



private class Row extends Thread{ \end{verbatim}

 \begin{verbatim}



	boolean[] row; int myRowNumber; Future[] row_k_step_k; Accumulator done;
	\end{verbatim}

 \begin{verbatim}



	Row( boolean[] row, \end{verbatim}

 \begin{verbatim}



	     int myRowNumber, \end{verbatim}

 \begin{verbatim}



	     Future[] row_k_step_k, \end{verbatim}

 \begin{verbatim}



	     Accumulator done){ \end{verbatim}

 \begin{verbatim}



		this.row=row; \end{verbatim}

 \begin{verbatim}



		this.myRowNumber=myRowNumber; \end{verbatim}

 \begin{verbatim}



		this.row_k_step_k=row_k_step_k; \end{verbatim}

 \begin{verbatim}



		this.done=done; \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	public void run() { \end{verbatim}

 \begin{verbatim}



	  try { \end{verbatim}

 \begin{verbatim}



	    int j,k; \end{verbatim}

 \begin{verbatim}



	    boolean[] row_k; \end{verbatim}

 \begin{verbatim}



	    for (k=0;k<row_k_step_k.length;k++) { \end{verbatim}


	    \begin{verbatim}



		    if (k==myRowNumber) \end{verbatim}

 \begin{verbatim}



			     row_k_step_k[k].setValue(row.clone());
			     \end{verbatim}

 \begin{verbatim}



		    else if (row[k]) { \end{verbatim}

 \begin{verbatim}



			    row_k = (boolean[])row_k_step_k[k].getValue();
			    \end{verbatim}

 \begin{verbatim}



			    for(j=0;j<row.length;j++) { \end{verbatim}


			    \begin{verbatim}



			        row[j] |= row_k[j]; \end{verbatim}


			        \begin{verbatim}



			    } \end{verbatim}

 \begin{verbatim}



		    } \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    boolean[][] result=(boolean[][])done.getData(); \end{verbatim}


	    \begin{verbatim}



	    result[myRowNumber]=row; \end{verbatim}

 \begin{verbatim}



	    done.signal(); \end{verbatim}

 \begin{verbatim}



	  } catch (InterruptedException ex){} \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 %\end{tabular}

 \begin{itemize}

\item{row[] : The contents of the row it is to work on, a boolean array.}

\item{myRowNumber : The number of its row, an integer.}

\item{row\_k\_step\_k : The array of futures that will contain the k th rows to
be used during the k th steps.}

\item{done : The accumulator into which to place its result.}

\end{itemize} The \texttt{Row} class's \texttt{run()} method does most of its
work in the \texttt{k} loop. This loop goes through the N steps of the
algorithm. If step \texttt{k} of the algorithm is equal to the number of the row
that this thread is processing, it stores a copy of its row in the \texttt{k} th
element of the array of futures, row\_k\_step\_k. Otherwise, it checks to see if
it needs the \texttt{k} th row. It will only need it if the \texttt{k} th
element of its row, \texttt{row[k]} , is true. If it needs it, it waits for it
to be computed and fetches the value

\texttt{row\_k\_step\_k[k].getValue()} and disjoins it into its own row in the
\texttt{for (j...)} loop.

When the loop is done, it gets a reference to the array of rows in the
accumulator \texttt{done} , puts its row into the result matrix, and signals its
completion.

One thing to notice about this code is that the \texttt{Row} threads do not run
lock stepped. There is no barrier to synchronize them. They can be running with
different values of \texttt{k} . The only synchronization in their main loops is
that when one thread needs the \texttt{k} th row, it fetches it from a future.
This will delay it if the row hasn't been computed yet.

This code provides a baseline implementation for us. We want to do the same
thing with chores, rather than threads. The problem we will face is that the
threads block in the middle. They block trying to get the value out of a future
inside an \texttt{if} statement inside a loop. It is not trivial to rearrange
this code so that calling a \texttt{run()} method will execute the next chore.

\subsection{WarshallC2} The first technique we use to convert
\texttt{WarshallC1} to chores makes the body of the \texttt{Row} 's
\texttt{run()} method a loop containing a \texttt{switch} statement. A program
counter variable \texttt{pc} will select which code to execute next. This means
the control structures of \texttt{WarshallC1} 's \texttt{Row} thread will have
to be hand translated to blocks of code that can jump to each other by assigning
to the \texttt{pc} field. This converts a structured program into one containing
the equivalent of \texttt{goto} statements, which damages the clarity of the
code.

The overall structure of \texttt{WarshallC2} is shown in
\ref{chores.#id(80784)}[MISSING HREF] . \texttt{WarshallC2} is created with a
\texttt{numThreads} parameter to control the number of threads that will be
created to compute the transitive closure. Private class \texttt{Row} will be
responsible for computing a particular row. This version of \texttt{Row}
implements \texttt{Runnable,} rather than extending \texttt{Thread} ; it will be
placed in a runqueue to execute chores, rather than running as a thread. Method
\texttt{closure()} has the same interface as in \texttt{WarshallDF1} and
\texttt{WarshallC1} ; it is given a boolean matrix, and it computes a transitive
closure matrix without modifying its input.

%\begin{tabular} 

Overall structure of WarshallC2 \begin{verbatim}



class WarshallC2{ \end{verbatim}

 \begin{verbatim}



 int numThreads; \end{verbatim}

 \begin{verbatim}



 public WarshallC2(int numThreads){ \end{verbatim}

 \begin{verbatim}



	this.numThreads=numThreads; \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



 private class Row implements Runnable{ ... } \end{verbatim}

 \begin{verbatim}



 public boolean[][] closure(boolean[][] a) { ... } \end{verbatim}


 \begin{verbatim}



 } \end{verbatim}

 %\end{tabular}

 \texttt{WarshallC2} 's \texttt{closure()}
 method is shown in \ref{chores.#id(69033)}[MISSING HREF] . Its major
 differences from the \texttt{closure()} method of \texttt{WarshallC1} is that
 it uses a run queue to limit the number of threads that will be used in the
 transitive closure.

%\begin{tabular} 

closure() method of WarshallC2 \begin{verbatim}



 public boolean[][] closure(boolean[][] a) { \end{verbatim}

 \begin{verbatim}



	int i; \end{verbatim}

 \begin{verbatim}



	RunQueue rq=new RunQueue(numThreads); \end{verbatim}

 \begin{verbatim}



	 ff=new (rq); \end{verbatim}

 \begin{verbatim}



	Future[] kthRows=new Future[a.length]; \end{verbatim}

 \begin{verbatim}



	for (i=0;i<kthRows.length;++i) \end{verbatim}

 \begin{verbatim}



		kthRows[i]=ff.make(); \end{verbatim}

 \begin{verbatim}



	Accumulator done=new Accumulator(a.length, \end{verbatim}


	\begin{verbatim}



		new boolean[a.length][]); \end{verbatim}

 \begin{verbatim}



	for (i=0;i<a.length;i++) { \end{verbatim}

 \begin{verbatim}



		rq.run(new Row((boolean[])a[i].clone(),i,kthRows,done));
		\end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	boolean[][] result=null; \end{verbatim}

 \begin{verbatim}



	try { \end{verbatim}

 \begin{verbatim}



	    result=(boolean[][])done.getFuture().getValue(); \end{verbatim}


	    \begin{verbatim}



	    rq.setMaxThreadsWaiting(0); \end{verbatim}

 \begin{verbatim}



	} catch (InterruptedException ex){} \end{verbatim}

 \begin{verbatim}



	return result; \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 The \texttt{closure()} method begins by creating a
run queue \texttt{rq} that will create no more than \texttt{numThreads} threads
for a single transitive closure. It uses this run queue in the future factory
\texttt{ff} that it uses to initialize the \texttt{kthRows} futures. Now all the
chores that are dispatched when these futures are assigned will be placed in
\texttt{rq} and will be restricted to run in no more than \texttt{numThreads}
threads at a time.

When \texttt{closure()} creates the \texttt{Row} objects, the objects are set
running by being placed in \texttt{rq} . Again, no more than \texttt{numThreads}
threads can process them at a time.

At the end, the \texttt{closure()} method sets the maximum number of threads
that may be waiting in the run queue to zero. This will force the waiting
threads to terminate. If this weren't done, the threads would wait around until
they timed out.

The overall structure of the \texttt{Row} class is shown in
\ref{chores.#id(63753)}[MISSING HREF] . The major addition is the \texttt{int}
field \texttt{pc} (initially zero), which controls which chore will execute when
\texttt{run()} is called.

%\begin{tabular} 

Row class of WarshallC2 \begin{verbatim}



 private class Row implements Runnable{ \end{verbatim}

 \begin{verbatim}



	boolean[] row; \end{verbatim}

 \begin{verbatim}



	int myRowNumber; \end{verbatim}

 \begin{verbatim}



	Future[] row_k_step_k; \end{verbatim}

 \begin{verbatim}



	Accumulator done; \end{verbatim}

 \begin{verbatim}



	int pc=0; \end{verbatim}

 \begin{verbatim}



	int j,k; \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	Row( boolean[] row, \end{verbatim}

 \begin{verbatim}



	     int myRowNumber, \end{verbatim}

 \begin{verbatim}



	     Future[] row_k_step_k, \end{verbatim}

 \begin{verbatim}



	     Accumulator done){ \end{verbatim}

 \begin{verbatim}



		this.row=row; \end{verbatim}

 \begin{verbatim}



		this.myRowNumber=myRowNumber; \end{verbatim}

 \begin{verbatim}



		this.row_k_step_k=row_k_step_k; \end{verbatim}

 \begin{verbatim}



		this.done=done; \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	public void run() { ... } \end{verbatim}

 \begin{verbatim}



} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 \texttt{Row} 's \texttt{run()} method is shown in
\ref{chores.#id(82678)}[MISSING HREF] . It contains code for three chores,
indicated by \texttt{case 0:} , \texttt{case 1:} , and c \texttt{ase 2:} . The
body is a loop around a switch, \texttt{for(;;) try \lbrack switch(pc)} . The
loop allows one chore to jump directly to another by \texttt{pc=i; continue}
without having to go through a run queue. The functions of the chores are as
follows:

%\begin{tabular} 

Method run() from Row of WarshallC2 \begin{verbatim}



	public void run() { \end{verbatim}

 \begin{verbatim}



	  boolean[] row_k; \end{verbatim}

 \begin{verbatim}



	  for(;;) try { switch (pc) { \end{verbatim}

 \begin{verbatim}



  case 0: \end{verbatim}

 \begin{verbatim}



	    k=0; pc=1; \end{verbatim}

 \begin{verbatim}



  case 1: \end{verbatim}

 \begin{verbatim}



	    if (k>=row_k_step_k.length){ \end{verbatim}

 \begin{verbatim}



	        boolean[][] result=(boolean[][])done.getData(); \end{verbatim}


	        \begin{verbatim}



	    	    result[myRowNumber]=row; \end{verbatim}

 \begin{verbatim}



	    	    done.signal(); \end{verbatim}

 \begin{verbatim}



		         return; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    if (k==myRowNumber) { \end{verbatim}

 \begin{verbatim}



		    row_k_step_k[k].setValue(row.clone()); \end{verbatim}


		    \begin{verbatim}



		    k++; \end{verbatim}

 \begin{verbatim}



		    continue; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    if (!row[k]) { \end{verbatim}

 \begin{verbatim}



		    k++; \end{verbatim}

 \begin{verbatim}



		    continue; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    pc=2; \end{verbatim}

 \begin{verbatim}



	    if (!row_k_step_k[k].isSet()) { \end{verbatim}

 \begin{verbatim}



		    row_k_step_k[k].runDelayed(this); \end{verbatim}


		    \begin{verbatim}



		    return; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



  case 2: \end{verbatim}

 \begin{verbatim}



	    row_k = (boolean[])row_k_step_k[k].getValue(); \end{verbatim}


	    \begin{verbatim}



	    for(j=0;j<row.length;j++) { \end{verbatim}

 \begin{verbatim}



		    row[j] |= row_k[j]; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    pc=1; \end{verbatim}

 \begin{verbatim}



	    k++; \end{verbatim}

 \begin{verbatim}



	    continue; \end{verbatim}

 \begin{verbatim}



	  }//switch \end{verbatim}

 \begin{verbatim}



	 } catch (InterruptedException ex){} \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 \textbf{case 0:} Chore 0 starts the implicit
\texttt{k} loop by initializing \texttt{k} to zero, sets \texttt{pc} to one to
select the next chore and falls through to execute it immediately. Yes, this
could have been done a bit more simply by just having an initializer for
\texttt{k} in the class declaration, but we wanted to show that there is usually
some initialization code executed only at the beginning.case 1:Chore 1 is the
top of the \texttt{k} loop. First, it checks to see if \texttt{k} is greater
than the number of steps in the algorithm. If so, we are done. In
\texttt{WarshallC1,} the code to finish the computation is at the bottom,
following the \texttt{k} loop, but here we have moved the code into the
loop.Next, chore 1 checks to see whether it has the \texttt{k} th row. If so, it
puts it in the proper future in the array row\_k\_step\_k, increments \texttt{k}
, and loops back to immediately execute chore 1 again for the next value of
\texttt{k} .Similarly, if we don't need the \texttt{k} th row (i.e., our
\texttt{row[k]} is false), we increment \texttt{k} and loop back to immediately
execute chore 1 again.If we do need the \texttt{k} th row, we set \texttt{pc=2}
to choose chore 2 to run next. We check to see if the future containing the
\texttt{k} th row has been set yet. If it has, we just fall through into chore
2. If not, we run ourselves delayed on the future, which will wake us up to run
chore 2 when the value is present.case 2:Chore 2 fetches and uses the \texttt{k}
th row during step \texttt{k} of the algorithm. We only enter chore 2 when we
know that the future in row\_k\_step\_k[k] has a value in it. Thus, the
\texttt{getValue} will not block.We end by disjoining the \texttt{k} th row with
our row, incrementing \texttt{k} , assigning \texttt{pc=1} to go back to the top
of the loop, and then starting chore 1 immediately by going on to the next
iteration. The \texttt{continue} here is for consistency. It isn't needed.The
performance of \texttt{WarshallC2} on a dual-processor kernel-thread Java system
is shown in \ref{Chores.#id(70388)}[MISSING HREF] . The number of threads barely
made a difference.

\includegraphics{figures/chores-7}

\subsection{WarshallC3} By representing continuations as cases in a
\texttt{switch} statement, \texttt{WarshallC2} obscures the code. There is no
mnemonic meaning associated with these de facto numeric statement labels. Just
using the same class for several different chores may obscure the meaning.

\texttt{WarshallC3} tries to be clearer by putting different chores in different
classes. The names of the classes try to make the intention of the code clearer.

The overall structure of \texttt{WarshallC3} is shown in
\ref{chores.#id(31017)}[MISSING HREF] . Here, class \texttt{Row} itself has two
inner classes. \texttt{Row.Loop} is the top of the \texttt{k} loop in Warshall's
algorithm, corresponding to \texttt{case 1} in \texttt{WarshallC1} . Class
\texttt{Row.UpdateRow} corresponds to \texttt{case 2} . It handles fetching the
\texttt{k} th row and disjoining it with \texttt{row} .

%\begin{tabular} 

Overall structure of WarshallC3 \begin{verbatim}



class WarshallC3{ \end{verbatim}

 \begin{verbatim}



 int numThreads; \end{verbatim}

 \begin{verbatim}



 public WarshallC3(int numThreads){ \end{verbatim}

 \begin{verbatim}



	this.numThreads=numThreads; \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



 private class Row implements Runnable{ \end{verbatim}

 \begin{verbatim}



		Row( boolean[] row, \end{verbatim}

 \begin{verbatim}



	     int myRowNumber, \end{verbatim}

 \begin{verbatim}



	     Future[] row_k_step_k, \end{verbatim}

 \begin{verbatim}



	     Accumulator done, \end{verbatim}

 \begin{verbatim}



	     RunQueue rq){ ... \end{verbatim}

 \begin{verbatim}



		} \end{verbatim}

 \begin{verbatim}



	class Loop implements Runnable { \end{verbatim}

 \begin{verbatim}



	  public void run() { \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	Loop loop=new Loop(); \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	class UpdateRow implements Runnable { \end{verbatim}

 \begin{verbatim}



	  public void run() {...} \end{verbatim}

 \begin{verbatim}



    } \end{verbatim}

 \begin{verbatim}



	UpdateRow updateRow=new UpdateRow(); \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	public void run() {// for Row class \end{verbatim}

 \begin{verbatim}



		k=0; \end{verbatim}

 \begin{verbatim}



		rq.run(loop); \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



 public boolean[][] closure(boolean[][] a) { ...} \end{verbatim}


 \begin{verbatim}



 } \end{verbatim}

 %\end{tabular}

 Method \texttt{closure()} , shown in
 \ref{chores.#id(93110)}[MISSING HREF] , is fundamentally the same as in
 \texttt{WarshallC2} . The only change other than renaming is having to provide
 \texttt{Row} with a run queue to use. The chores in \texttt{Row} objects will
 need this to schedule their successors.

%\begin{tabular} 

closure() method of WarshallC3 \begin{verbatim}



 public boolean[][] closure(boolean[][] a) { \end{verbatim}

 \begin{verbatim}



	int i; \end{verbatim}

 \begin{verbatim}



	RunQueue rq=new RunQueue(numThreads); \end{verbatim}

 \begin{verbatim}



	FutureFactory ff=new FutureFactory(rq); \end{verbatim}

 \begin{verbatim}



	Future[] kthRows=new Future[a.length]; \end{verbatim}

 \begin{verbatim}



	for (i=0;i<kthRows.length;++i) \end{verbatim}

 \begin{verbatim}



		kthRows[i]=ff.make(); \end{verbatim}

 \begin{verbatim}



	Accumulator done=new Accumulator(a.length, \end{verbatim}


	\begin{verbatim}



		new boolean[a.length][]); \end{verbatim}

 \begin{verbatim}



	for (i=0;i<a.length;i++) { \end{verbatim}

 \begin{verbatim}



		rq.run( \end{verbatim}

 \begin{verbatim}



			new Row((boolean[])a[i].clone(),i,kthRows,done,rq));
			\end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	boolean[][] result=null; \end{verbatim}

 \begin{verbatim}



	try { \end{verbatim}

 \begin{verbatim}



	    result=(boolean[][])done.getFuture().getValue(); \end{verbatim}


	    \begin{verbatim}



	    rq.setMaxThreadsWaiting(0); \end{verbatim}

 \begin{verbatim}



	} catch (InterruptedException ex){} \end{verbatim}

 \begin{verbatim}



	return result; \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 The structure of class \texttt{Row} is shown in
\ref{chores.#id(63260)}[MISSING HREF] . The major function of \texttt{Row} is to
hold the data shared by the local classes \texttt{Loop} and \texttt{UpdateRow} .
When a \texttt{Row} is created, it creates a single instance of each of the
local classes. The \texttt{run()} method for \texttt{Row} has the same
functionality as \texttt{case 0} in \texttt{WarshallC2} . It initializes
\texttt{k} and runs the chore contained in local class \texttt{Loop} .

%\begin{tabular}

Row class of WarshallC3 \begin{verbatim}



 private class Row implements Runnable{ \end{verbatim}

 \begin{verbatim}



	boolean[] row; \end{verbatim}

 \begin{verbatim}



	int myRowNumber; \end{verbatim}

 \begin{verbatim}



	Future[] row_k_step_k; \end{verbatim}

 \begin{verbatim}



	Accumulator done; \end{verbatim}

 \begin{verbatim}



	RunQueue rq; \end{verbatim}

 \begin{verbatim}



	int j,k; \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	Row( boolean[] row, \end{verbatim}

 \begin{verbatim}



	     int myRowNumber, \end{verbatim}

 \begin{verbatim}



	     Future[] row_k_step_k, \end{verbatim}

 \begin{verbatim}



	     Accumulator done, \end{verbatim}

 \begin{verbatim}



	     RunQueue rq){ \end{verbatim}

 \begin{verbatim}



		this.row=row; \end{verbatim}

 \begin{verbatim}



		this.myRowNumber=myRowNumber; \end{verbatim}

 \begin{verbatim}



		this.row_k_step_k=row_k_step_k; \end{verbatim}

 \begin{verbatim}



		this.done=done; \end{verbatim}

 \begin{verbatim}



		this.rq=rq; \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	class Loop implements Runnable { \end{verbatim}

 \begin{verbatim}



	  public void run() { ... } \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	Loop loop=new Loop(); \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	class UpdateRow implements Runnable { \end{verbatim}

 \begin{verbatim}



	  public void run() {...} \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



	UpdateRow updateRow=new UpdateRow(); \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	public void run() {// for Row class \end{verbatim}

 \begin{verbatim}



		k=0; \end{verbatim}

 \begin{verbatim}



		rq.run(loop); \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



 } \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 \texttt{Row} 's \texttt{Loop} class is shown in
\ref{chores.#id(46460)}[MISSING HREF] . The body of \texttt{Loop} 's
\texttt{run()} method is contained in a \texttt{for(;;)} loop, so that it can
keep on executing as long as possible, increasing the grain size.

%\begin{tabular} 

Loop from Row of WarshallC3 \begin{verbatim}



	class Loop implements Runnable { \end{verbatim}

 \begin{verbatim}



	  public void run() { \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	   for(;;) { \end{verbatim}

 \begin{verbatim}



	    if (k>=row_k_step_k.length){ \end{verbatim}

 \begin{verbatim}



	        	boolean[][] result=(boolean[][])done.getData();
	        	\end{verbatim}

 \begin{verbatim}



	    	    result[myRowNumber]=row; \end{verbatim}

 \begin{verbatim}



	    	    done.signal(); \end{verbatim}

 \begin{verbatim}



		    return; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    if (k==myRowNumber) { \end{verbatim}

 \begin{verbatim}



		    row_k_step_k[k].setValue(row.clone()); \end{verbatim}


		    \begin{verbatim}



		    k++; \end{verbatim}

 \begin{verbatim}



		    continue; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    if (!row[k]) { \end{verbatim}

 \begin{verbatim}



		    k++; \end{verbatim}

 \begin{verbatim}



		    continue; \end{verbatim}

 \begin{verbatim}



	    } \end{verbatim}

 \begin{verbatim}



	    row_k_step_k[k].runDelayed(updateRow); \end{verbatim}


	    \begin{verbatim}



	    return; \end{verbatim}

 \begin{verbatim}



	   } \end{verbatim}

 \begin{verbatim}



	  } \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 \texttt{Loop} first checks to see if it is done
with its part of the algorithm (i.e., if k >= row\_k\_step\_k.length), and if
so, it stores its part of the result and terminates. Next, it checks to see if
\texttt{k} is equal to its row number, and if so, it stores a copy of its row in
the \texttt{k} th future in row\_k\_step\_k for the other chores to access and
goes on to the next iteration.

Then, \texttt{Loop} checks to see if it needs the \texttt{k} th row to update
its own. It will need it if the \texttt{k} th element of its row is true. If it
doesn't need the \texttt{k} th row, it increments \texttt{k} and loops back to
the top of its code. If it does need the \texttt{k} th row, it run delays its
\texttt{updateRow} on row\_k\_step\_k[k] and returns to give up the thread it is
running on. When the \texttt{k} th row is available, this row's
\texttt{UpdateRow} chore will be scheduled.

The \texttt{UpdateRow} chore will get the \texttt{k} th row out of the future in
row\_k\_step\_k[k] and disjoins it with its own row. Then, it increments
\texttt{k} and schedules chore \texttt{Loop} to execute.

%\begin{tabular} 

UpdateRow from Row of WarshallC3 \begin{verbatim}



\end{verbatim}

 \begin{verbatim}



	class UpdateRow implements Runnable { \end{verbatim}

 \begin{verbatim}



	  public void run() { \end{verbatim}

 \begin{verbatim}



	    boolean[] row_k; \end{verbatim}

 \begin{verbatim}



	    try { \end{verbatim}

 \begin{verbatim}



		    row_k = (boolean[]) \end{verbatim}

 \begin{verbatim}



                 row_k_step_k[k].getValue(); \end{verbatim}

 \begin{verbatim}



		    for(j=0;j<row.length;j++) { \end{verbatim}

 \begin{verbatim}



		        row[j] |= row_k[j]; \end{verbatim}

 \begin{verbatim}



		    } \end{verbatim}

 \begin{verbatim}



		    k++; \end{verbatim}

 \begin{verbatim}



		    rq.run(loop); \end{verbatim}

 \begin{verbatim}



	    } catch (InterruptedException ex){} \end{verbatim}

 \begin{verbatim}



	  } \end{verbatim}

 \begin{verbatim}



	} \end{verbatim}

 \begin{verbatim}



\end{verbatim}

 %\end{tabular}

 In comparison to \texttt{WarshallC2} ,
\texttt{WarshallC3} has a couple of notable differences. \texttt{WarshallC3} 's
chores are named and individually packaged, which is probably more intuitive
than the numbers in \texttt{WarshallC2} . Of course, \texttt{WarshallC2} could
name its chores by use of some \texttt{final int} declarations. An efficiency
problem for \texttt{WarshallC3} is that it schedules other chores by placing
objects on a run queue, rather than just falling through or jumping to them.
This can take a lot more instruction executions. It can be ameliorated somewhat
by having one chore immediately execute the next by calling the other's
\texttt{run()} method. For example, the \texttt{run()} method of \texttt{Row}
could end by calling

\texttt{loop.run();} rather than

\texttt{rq.run(loop);} Class \texttt{UpdateRow} could do the same thing. One
might go further and have \texttt{Loop} check whether the future
row\_k\_step\_k[k] is set and call \texttt{updateRow.run()} , rather than
\texttt{runDelayed()} . The problem here is that Java is not required to
optimize tail-end recursion. Each call can grow the thread's stack deeper, and
if one is not careful, the thread could run out of stack space.

The performance of \texttt{WarshallC3} on a dual-processor, kernel-threads Java
implementation is shown in \ref{Chores.#id(41794)}[MISSING HREF] . Any number of
threads greater than one ran faster than one thread, but other than that, there
was not much difference in run times among the different numbers of threads.

\includegraphics{figures/chores-8}

\section{Chapter Wrap-up} This chapter is devoted to programming with chores. A
chore is a small amount of computation that communicates with other chores only
at its beginning and end.The advantage of using chores is that they needn't be
handed to threads until the chores they depend upon have completed; hence, they
do not block while holding threads. This allows run queues to limit the number
of threads created without fear of deadlock. This can save the expense of
creating a multitude of threads.

The use of chores requires two things:

\begin{itemize}

\item{Synchronization objects that support chore scheduling and}

\item{A collection of chore-programming techniques.}

\end{itemize} Most of the thread package synchronization classes have versions
that allow chore scheduling. All of them implement the \texttt{RunDelayed}
interface. They implement method \texttt{runDelayed(Runnable r)} , which puts
\texttt{r} into a run queue when some event occurs.

The class \texttt{Future} , a subclass of \texttt{SimpleFuture} , will wake up
the delayed runnables, placing them into a run queue when the future has its
value set. The runnables are thus delayed on the future the same as are threads
that call \texttt{getValue()} . A \texttt{FutureFactory} object generates
futures that all place runnables on the same run queue.

The chore programming techniques include the use of job jars, macro dataflow,
chore graphs, and continuations.

\section{Exercises} 1. For each example of vector addition, \texttt{add} a third
vector (7.0,8.0,9.0) to the sum of the other two, and store the result in
\texttt{f3} .

For \texttt{TestVadd2} , have the \texttt{add} of the first two vectors store
its result directly in the \texttt{Binop} object for the second addition.

For \texttt{TestVadd3} , have the add method of the first two vectors pass its
result directly to the fetch of the third operand.

2. Change \texttt{WarshallC1} , \texttt{WarshallC2} , and \texttt{WarshallC3} to
update the input array in place, rather than returning a new array.

3. Rewrite \texttt{WarshallDF1} to use a class \texttt{RowUpdateFactory} , a
factory with recycling, to make \texttt{RowUpdate} objects. Compare the running
times with and without the factory. This should be instructive, even on a
single-processor machine.

4. Continue Exercise 3 by adding a semaphore to \texttt{RowUpdateFactory} to
limit the number of \texttt{RowUpdate} objects that can be created. This will
force the thread generating the \texttt{RowUpdate} objects to wait for
recycling. It is the equivalent of using a bounded buffer as a run queue. It
will prevent the program from being flooded with \texttt{RowUpdate} objects.
Experiment with different limits on the initial semaphore count, and see if it
improves or worsens performance.

5. It is possible that updating individual rows gives too small a grain size for
Warshall's algorithm. Rewrite \texttt{WarshallDF1} , \texttt{WarshallC2} , or
\texttt{WarshallC3} to update blocks of several consecutive rows in each chore,
rather than just one row. Does it make a difference?
\be
\section{}
